package com.code.leetcode.center50;

import com.code.leetcode.center50.utils.Node;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/27 9:59
 */
public class The116 {
    Deque<Node> deque = new ArrayDeque<>();

    public Node connect(Node root) {
        if (root == null) return null;

        deque.addLast(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                Node node = deque.pollFirst();
                if (i < size - 1) {
                    node.next = deque.peekFirst();
                }
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
            }
        }
        return root;
    }

    /**
     * 利用完美二叉树进行构建
     * @param root
     * @return
     */

    public Node connectB(Node root) {
        dfs(root, null);
        return root;
    }

    public void dfs(Node node, Node next) {
        if (node != null) {
            node.next = next;
            dfs(node.left, node.right);
            dfs(node.right, node.next != null ? node.next.left : null);
        }
    }


}
